package com.heyqing.medium.day3;

import java.util.*;
import java.util.stream.Collectors;

/**
 * ClassName:ThreeSum
 * Package:com.heyqing.medium.day3
 * Description:
 *
 * @Date:2024/10/4
 * @Author:Heyqing
 */
public class ThreeSum {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> record = new ArrayList<>();
        for(int k = 0; k < nums.length - 2; k++){
            if(nums[k] > 0) break;
            if(k > 0 && nums[k] == nums[k - 1]) continue;
            int i = k + 1, j = nums.length - 1;
            while(i < j){
                int sum = nums[k] + nums[i] + nums[j];
                if(sum < 0){
                    while(i < j && nums[i] == nums[++i]);
                } else if (sum > 0) {
                    while(i < j && nums[j] == nums[--j]);
                } else {
                    record.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j])));
                    while(i < j && nums[i] == nums[++i]);
                    while(i < j && nums[j] == nums[--j]);
                }
            }
        }
        return record;
    }


//    List<List<Integer>> record = new ArrayList<>();
//        for (int i = 0; i < nums.length - 2; i++) {
//        for (int j = i + 1; j < nums.length - 1; j++) {
//            for (int k = j + 1; k < nums.length; k++) {
//                if (nums[i] + nums[j] + nums[k] == 0) {
//                    List<Integer> temp = Arrays.asList(nums[i], nums[j], nums[k]);
//                    if (isNotContains(temp, record)) {
//                        record.add(temp);
//                    }
//                }
//            }
//        }
//    }
//        return record;
//
//    private boolean isNotContains(List<Integer> temp, List<List<Integer>> record) {
//        if (record.size() == 0) return true;
//        Set<Integer> tempSet = new HashSet<>(temp);
//        for (List<Integer> list : record) {
//            Set<Integer> listSet = new HashSet<>(list);
//            if (tempSet.equals(listSet)) {
//                return false;
//            }
//        }
//        return true;
//    }
}
